template <const int N>
struct AC_Automaton {
	int q[N], fail[N], son[N][26], f[N];
	int tot, hd, tl;

	int insert(const char *s) {
		int p = 0;
		for (int i = 0, n = strlen(s); i < n; i++) {
			int nxt = s[i] - 'a';
			if (!son[p][nxt]) {
				son[p][nxt] = ++tot;
			}
			p = son[p][nxt];
		}
		return p;
	}

	void clean() {
		tot = 0;
		for (int i = 0; i <= N; i++) {
			f[i] = fail[i] = 0;
			memset(son[i], 0, sizeof(son[i]));
		}
	}

	void build() {
		hd = 1, tl = 0;
		for (int i = 0; i < 26; i++) {
			if (son[0][i]) {
				q[++tl] = son[0][i];
			}
		}
		while (hd <= tl) {
			int u = q[hd++];
			for (int i = 0; i < 26; i++) {
				int v = son[u][i];
				if (!v) {
					son[u][i] = son[fail[u]][i];
					continue;
				}
				fail[v] = son[fail[u]][i];
				q[++tl] = v;
			}
		}
	}

	void query(const char *s) {
		int p = 0;
		for (int i = 0, n = strlen(s); i < n; i++) {
			int nxt = s[i] - 'a';
			p = son[p][nxt];
			f[p]++;
		}

		// 确保已经build完成,按照倒序进行dp
		for (int i = tl; i >= 1; i--) {
			int j = fail[q[i]];
			f[j] += f[q[i]];
		}
	}
};
AC_Automaton<500001> ac;